package astar;

import java.util.LinkedList;
import domain.Board;
import domain.Square;
import domain.SquareWall;
import domain.Game.action;

public class Bfs {
	public static LinkedList<action> pathToNearestFlag(Square start, Board board){
		LinkedList<action> pathToFlag=new LinkedList<action>();
		BfsNode [][] arrGraph=new BfsNode[board.getNumberOfRows()][board.getNumberOfColumns()];
		//Vector<BfsNode> nodes= new Vector<BfsNode>();
		//creating the nodes.
		createNodes(board, arrGraph);
			
		//creating vertices
		createVertics(board, arrGraph);
		
		
		
		
		
		BfsNode startPoint=arrGraph[start.getRow()][start.getColumn()];
		pathToFlag=findClosestFlag(startPoint);
		return pathToFlag;
	}

	private static LinkedList<action> findClosestFlag(BfsNode startPoint) {
		LinkedList<BfsNode> Q=new LinkedList<BfsNode>();
		//Initialization
		boolean foundFlag=false;
		startPoint.setColorGray();
		BfsNode temp;
		//enqueue start [stage 9 in Corman]
		Q.addLast(startPoint);
		while(foundFlag==false&&!Q.isEmpty()){
			
			temp=Q.removeFirst();
			if(temp.hasFlag()){
				return createPath(temp);
			}
			if(temp.getUp()!=null){
				if(temp.getUp().isWhite()){
					temp.getUp().setColorGray();
					temp.getUp().setPre(action.UP);
					temp.getUp().setPreNode(temp);
					Q.addLast(temp.getUp());
				}
			}
			if(temp.getRight()!=null){
				if(temp.getRight().isWhite()){
					temp.getRight().setColorGray();
					temp.getRight().setPre(action.RIGHT);
					temp.getRight().setPreNode(temp);
					Q.addLast(temp.getRight());
				}
			}
			if(temp.getDown()!=null){
				if(temp.getDown().isWhite()){
					temp.getDown().setColorGray();
					temp.getDown().setPre(action.DOWN);
					temp.getDown().setPreNode(temp);
					Q.addLast(temp.getDown());
				}
			}
			if(temp.getLeft()!=null){
				if(temp.getLeft().isWhite()){
					temp.getLeft().setColorGray();
					temp.getLeft().setPre(action.LEFT);
					temp.getLeft().setPreNode(temp);
					Q.addLast(temp.getLeft());
				}
			}
			temp.setColorBlack();
		}//end of while
		
		return null;//if null is returned than there is no flag to reach.
	}

	private static LinkedList<action> createPath(BfsNode flagNode) {
		BfsNode temp=flagNode;
		LinkedList<action> path=new LinkedList<action>();
		
		while(temp.getPreDirection()!=null){
			path.addFirst(temp.getPreDirection());
			temp=temp.getPreNode();
		}
		return path;
	}

	private static void createVertics(Board board, BfsNode[][] arrGraph) {
		for (int row = 1; row < board.getNumberOfRows()-1; row++) {
			for (int column = 1; column < board.getNumberOfColumns()-1; column++) {
				if(!(board.getSquare(row, column) instanceof SquareWall)){
					//up
					if(!(board.getSquare(row-1, column) instanceof SquareWall)){
						arrGraph[row][column].setUp(arrGraph[row-1][column]);
					}
					//right
					if(!(board.getSquare(row, column+1) instanceof SquareWall)){
						arrGraph[row][column].setRight(arrGraph[row][column+1]);
					}
					//down
					if(!(board.getSquare(row+1, column) instanceof SquareWall)){
						arrGraph[row][column].setDown(arrGraph[row+1][column]);
					}
					//left
					if(!(board.getSquare(row, column-1) instanceof SquareWall)){
						arrGraph[row][column].setLeft(arrGraph[row][column-1]);
					}
				}	
			}
		}
	}//end of createVertics

	private static void createNodes(Board board, BfsNode[][] arrGraph) {
		for (int row = 0; row < board.getNumberOfRows(); row++) {
			for (int column = 0; column < board.getNumberOfColumns(); column++) {
				if(!(board.getSquare(row, column) instanceof SquareWall)){
					arrGraph[row][column]=new BfsNode(row, column);
					if(board.getSquare(row, column).getFlag()!=null){
						arrGraph[row][column].setFalgToTrue();
					}
				}
				
			}
		}
	}//end of creatNodes
}//end of class